package com.lzq.leetcode.hoot100;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class s239 {

    public int[] maxSlidingWindow(int[] nums, int k) {

        int len = nums.length;
        int[] nextH = new int[len];
        Deque<Integer> dq = new LinkedList<>();

        for (int i=len-1; i>=0; i--) {
            while (!dq.isEmpty() && nums[dq.getFirst()] <= nums[i]) {
                dq.pollFirst();
            }

            nextH[i] = dq.isEmpty() ? -1 : dq.getFirst();
            dq.addFirst(i);
        }

        // 实现
        int p = 0;
        int[] ans = new int[len - k + 1];
        for (int end = k-1; end < len; end++) {
            int star = end - k + 1;

            if (p < star) {
                p = star;
            }
            while (true) {
                int tp = nextH[p];
                if (tp != -1 && tp <= end) {
                    p = tp;
                } else {
                    break;
                }
            }

            ans[star] = nums[p];
        }
        return ans;
    }

    public static void main(String[] args) {
        s239 s239 = new s239();
        System.out.println(s239.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3));
    }
}
